﻿//扫雷游戏(medium): https://leetcode.cn/problems/minesweeper/description/
class Solution {
public:
    int m,n;
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        m=board.size(),n=board[0].size();
        int i=click[0],j=click[1];
        if(board[i][j]=='M')
        {
            board[i][j]='X';
            return board;
        }
        dfs(board,i,j);
        return board;
    }
     int dx[8]={-1,0,1,-1,0,1,-1,1};
     int dy[8]={-1,-1,-1,1,1,1,0,0};
    void dfs(vector<vector<char>>& board,int i,int j)
    {
        if(board[i][j]=='E')//E
        {
            int count=0;
            for(int k=0;k<8;k++)
            {
                int x=dx[k]+i;  int y=dy[k]+j;
                if(x>=0&&x<m && y>=0&&y<n && board[x][y]=='M')
                {
                    count++;
                }
            }
           if(count) 
           {
                board[i][j]=count+'0';
                return; 
           }
            board[i][j]='B';
        }

         for(int k=0;k<8;k++)
          {
                int x=dx[k]+i;  int y=dy[k]+j;
                if(x>=0&&x<m && y>=0&&y<n&&board[x][y]=='E')  //E都有可能
                {
                    dfs(board,x,y);
                }
            }
            
    }
};

//衣橱整理(medium)：https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/description/
class Solution {
public:
    int count;
    int dx[2]={0,1};
    int dy[2]={1,0};
    bool vis[110][110];
    int m,n;
    int wardrobeFinishing(int _m, int _n, int cnt) {
        m=_m,n=_n;
        dfs(0,0,cnt);
        return count;
    }
    void dfs(int i,int j,int cnt)
    {
        vis[i][j]=true;
        int sum=Digit(i)+Digit(j);
        if(sum>cnt)
        {
            return;
        }
        count++;
        for(int k=0;k<2;k++)
        {
            int x=dx[k]+i;   int y=dy[k]+j;
            if(x>=0&&x<m&&y>=0&&y<n && !vis[x][y])
            {
                dfs(x,y,cnt);
            }
        }
    }
    int Digit(int num)
    {
        int x=0;
        while(num)
        {
            x+=num%10;
            num/=10;
        }
        return x;
    }
};